﻿#pragma once
#include "BitSet.h"
#include <string>
namespace The_Song_of_the_end_of_the_world
{
	struct HashFuncBKDR
	{
	/// @detail 本算法由于在Brian Kernighan与Dennis Ritchie的《The C Programming Language》        
	//一书中所展示而得名，是⼀种简单快捷的hash算法，
	// 也是Java目前采用的的字符串的Hash算法累乘因⼦为31。

		size_t operator()(const string & s)
		{
			size_t hash = 0;
			for (auto& ch : s)
			{
				hash *= 31;
				hash += ch;
			}
			return hash;
		}
	};
	struct HashFuncAP
	{
		// 由Arash Partow发明的⼀种hash算法。

		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (size_t i = 0; i < s.size(); i++)
			{
				if ((i & 1) == 0) // 偶数位字符
				{
					hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
				}
				else              // 奇数位字符
				{
					hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >>5)));
				}
			}
			return hash;
		}
	};
	struct HashFuncDJB
	{
		// 由Daniel J.Bernstein教授发明的⼀种hash算法。

		size_t operator()(const string& s)
		{
			size_t hash = 5381;
			for (auto& ch : s)
			{
				hash = hash * 33 ^ ch;
			}
			return hash;
		}
	};
	//X相当于布隆过滤器的M/N
	//N*X为M
	template<size_t N,
		size_t X = 6,
		class K = std::string,
		class Hash1 = HashFuncBKDR,
		class Hash2 = HashFuncAP,
		class Hash3 = HashFuncDJB>
	class BloomFilter
	{
	public:
		void Set(const K& key)
		{
			size_t hash1 = Hash1()(key) % M;
			size_t hash2 = Hash2()(key) % M;
			size_t hash3 = Hash3()(key) % M;
			_bs.set(hash1);
			_bs.set(hash2);
			_bs.set(hash3);
		}
		bool Test(const K& key)
		{
			size_t hash1 = Hash1()(key) % M;
			if (_bs.test(hash1) == false)
				return false;
			size_t hash2 = Hash2()(key) % M;
			if (_bs.test(hash2) == false)
				return false;
			size_t hash3 = Hash3()(key) % M;
			if (_bs.test(hash3) == false)
				return false;
			return true;
		}
		// 获取公式计算出的误判率        
		double getFalseProbability()
		{
			double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);
			return p;
		}
	private:
		static const size_t M = X * N;
		//我们实现位图是⽤vector,也就是堆上开的空间
		The_Song_of_the_end_of_the_world::BitSet<M> _bs;
			//std::bitset<M> _bs;
	   // vs下std的位图是开的静态数组，	M太⼤会存在崩的问题        
	   // // 解决⽅案就是bitset	对象整体new⼀下，空间就开到堆上了        
	   // //std::bitset<M>* _bs = new std::bitset<M>;
	};
}


